// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections.Generic;

namespace Microsoft.ML.Probabilistic.Compiler.Graphs
{
    /// <summary>
    /// A graph of nodes and edges.
    /// </summary>
    /// <typeparam name="NodeType">The type of a node handle.</typeparam>
    /// <remarks><p>
    /// This interface is intended for use by generic algorithms which can operate on any graph type.
    /// Nodes are treated as opaque handles, generated by the graph, which only the graph knows how to resolve.
    /// Some graph types might represent nodes as objects with edge data; other graphs might use integer indices or even strings.
    /// </p><p>
    /// This interface can be used for both directed and undirected graphs, though the methods only provide
    /// undirected information (i.e. all neighbors rather than sources vs. targets).
    /// See <see cref="IMutableGraph&lt;NodeType&gt;"/> for methods to modify a graph, and <see cref="IDirectedGraph&lt;NodeType&gt;"/>
    /// to get directed edge information.
    /// In this interface, edges are represented implicitly as (source, target) pairs.
    /// See <see cref="IGraph&lt;NodeType,EdgeType&gt;"/> for methods using explicit edge handles.
    /// </p></remarks>
    internal interface IGraph<NodeType>
    {
        /// <summary>
        /// Collection of node handles.
        /// </summary>
        /// <remarks>
        /// The methods Add(NodeType) and Contains(NodeType) which are defined by <see cref="ICollection&lt;NodeType&gt;"/>
        /// are not necessarily supported (in order to use them, you would have to have a valid node handle, which
        /// implies the node is already in the graph).  The methods Remove(NodeType) and Clear() are only supported
        /// by mutable graphs, and they are only guaranteed to remove node handles from the Nodes collection; 
        /// the edges connected to those nodes may still exist in the graph.
        /// </remarks>
        ICollection<NodeType> Nodes { get; }

        int EdgeCount();

        /// <summary>
        /// Number of adjacent nodes.
        /// </summary>
        /// <param name="node">A node handle.</param>
        /// <returns>The number of nodes adjacent to <paramref name="node"/>.</returns>
        /// <remarks>For a directed graph, this is the number of sources (parents) plus the number of targets (children) of <paramref name="node"/></remarks>
        int NeighborCount(NodeType node);

        // if NeighborsOf were an ICollection, it would subsume NeighborCount and ClearEdgesOf.
        // however, these would usually be slower than direct method calls on the graph.
        /// <summary>
        /// Adjacent nodes.
        /// </summary>
        /// <param name="node">A node handle.</param>
        /// <returns>The nodes adjacent to <paramref name="node"/></returns>
        /// <remarks>For a directed graph, this is the sources (parents) and targets (children) of <paramref name="node"/>, in any order.</remarks>
        IEnumerable<NodeType> NeighborsOf(NodeType node);

        /// <summary>
        /// Test for an edge.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <returns>True if an edge exists from <paramref name="source"/> to <paramref name="target"/></returns>
        /// <remarks>
        /// For some graph types, source and target are not required to be nodes in the graph.
        /// That is, ContainsEdge(source,target) can be true even if Nodes.Contains(source) is false.
        /// </remarks>
        bool ContainsEdge(NodeType source, NodeType target);
    }

    internal interface IMutableGraph<NodeType> : IGraph<NodeType>
    {
        NodeType AddNode();
        bool RemoveNodeAndEdges(NodeType node);
        void Clear();
        void AddEdge(NodeType source, NodeType target);
        bool RemoveEdge(NodeType source, NodeType target);
        void ClearEdges();
        void ClearEdgesOf(NodeType node);
    }

    internal interface IDirectedGraph<NodeType> : IGraph<NodeType>
    {
        int TargetCount(NodeType source);
        int SourceCount(NodeType target);
        IEnumerable<NodeType> TargetsOf(NodeType source);
        IEnumerable<NodeType> SourcesOf(NodeType target);
    }

    internal interface IMutableDirectedGraph<NodeType> : IDirectedGraph<NodeType>, IMutableGraph<NodeType>
    {
        void ClearEdgesOutOf(NodeType source);
        void ClearEdgesInto(NodeType target);
    }

    /// <summary>
    /// A graph with explicit edge handles.
    /// </summary>
    /// <typeparam name="NodeType">The type of a node handle.</typeparam>
    /// <typeparam name="EdgeType">The type of an edge handle.</typeparam>
    /// <remarks><p>
    /// This interface is intended for use by generic algorithms which can operate on any graph type.
    /// Nodes and edges are treated as opaque handles, generated by the graph, which only the graph knows how to resolve.
    /// As a consequence, the methods AddEdge(EdgeType) and ContainsEdge(EdgeType) are not necessarily supported, because
    /// in order to use them, you would have to have a valid edge handle, which implies the edge already exists in the graph.
    /// </p><p>
    /// This interface can be used for both directed and undirected graphs, though the methods only provide
    /// undirected information (i.e. all edges rather than in-edges vs. out-edges).
    /// See <see cref="IMutableGraph&lt;NodeType,EdgeType&gt;"/> for methods to modify a graph, and <see cref="IDirectedGraph&lt;NodeType,EdgeType&gt;"/>
    /// to get directed edge information.
    /// </p></remarks>
    internal interface IGraph<NodeType, EdgeType> : IGraph<NodeType>
    {
        IEnumerable<EdgeType> Edges { get; }

        /// <summary>
        /// Get an edge handle.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <returns>An edge handle if the edge exists and is unique.</returns>
        /// <exception cref="EdgeNotFoundException">If there is no edge from source to target.</exception>
        /// <exception cref="AmbiguousEdgeException">If there is more than one edge from source to target.</exception>
        EdgeType GetEdge(NodeType source, NodeType target);

        /// <summary>
        /// Get an edge handle.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <param name="edge">An edge handle if the edge exists and is unique, otherwise <c>default(EdgeType)</c>.</param>
        /// <returns>True if there is an edge from source to target.</returns>
        /// <exception cref="AmbiguousEdgeException">If there is more than one edge from source to target.</exception>
        /// <remarks>This method combines the functionality of ContainsEdge(source,target) and GetEdge(source,target).</remarks>
        bool TryGetEdge(NodeType source, NodeType target, out EdgeType edge);

        /// <summary>
        /// All edges connected to a node.
        /// </summary>
        /// <param name="node">A node handle.</param>
        /// <returns>All edges connected to <paramref name="node"/>.</returns>
        IEnumerable<EdgeType> EdgesOf(NodeType node);
    }

    /// <summary>
    /// A graph which may have parallel edges.
    /// </summary>
    /// <typeparam name="NodeType">The type of a node handle.</typeparam>
    /// <typeparam name="EdgeType">The type of an edge handle.</typeparam>
    internal interface IMultigraph<NodeType, EdgeType> : IGraph<NodeType, EdgeType>
    {
        /// <summary>
        /// Count the edges between nodes.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <returns>The number of edges from <paramref name="source"/> to <paramref name="target"/>.</returns>
        int EdgeCount(NodeType source, NodeType target);

        /// <summary>
        /// Get edge handles.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <returns>All edges from source to target.</returns>
        IEnumerable<EdgeType> EdgesLinking(NodeType source, NodeType target);

        /// <summary>
        /// Get an edge handle.
        /// </summary>
        /// <param name="source">A node handle.</param>
        /// <param name="target">A node handle.</param>
        /// <param name="edge">An edge handle if an edge exists, otherwise <c>default(EdgeType)</c>.</param>
        /// <returns>True if there is an edge from source to target.</returns>
        /// <remarks>This method combines the functionality of ContainsEdge(source,target) and GetAnyEdge(source,target).</remarks>
        bool AnyEdge(NodeType source, NodeType target, out EdgeType edge);
    }

    internal interface IMutableGraph<NodeType, EdgeType> : IGraph<NodeType, EdgeType>, IMutableGraph<NodeType>
    {
        new EdgeType AddEdge(NodeType source, NodeType target);
        bool RemoveEdge(EdgeType edge);
    }

    internal interface IDirectedGraph<NodeType, EdgeType> : IGraph<NodeType, EdgeType>, IDirectedGraph<NodeType>
    {
        NodeType SourceOf(EdgeType edge);
        NodeType TargetOf(EdgeType edge);
        IEnumerable<EdgeType> EdgesOutOf(NodeType source);
        IEnumerable<EdgeType> EdgesInto(NodeType target);
    }

    internal interface IMutableDirectedGraph<NodeType, EdgeType> : IDirectedGraph<NodeType, EdgeType>, IMutableGraph<NodeType, EdgeType>, IMutableDirectedGraph<NodeType>
    {
    }

    internal class EdgeNotFoundException : Exception
    {
        public EdgeNotFoundException()
        {
        }

        public EdgeNotFoundException(object source, object target)
            : base("no edge from " + source + " to " + target)
        {
        }
    }

    internal class AmbiguousEdgeException : Exception
    {
        public AmbiguousEdgeException()
        {
        }

        public AmbiguousEdgeException(object source, object target)
            : base("ambiguous edge from " + source + " to " + target)
        {
        }
    }

    // note that "labeled graph" means something different in graph theory:
    // http://mathworld.wolfram.com/LabeledGraph.html
    internal interface ILabeledGraph<NodeType, LabelType> : IGraph<NodeType>
    {
        new ILabeledCollection<NodeType, LabelType> Nodes { get; }
    }

    internal interface ILabeledEdgeGraph<NodeType, EdgeType> : IGraph<NodeType>
    {
        void AddEdge(NodeType fromNode, NodeType toNode, EdgeType label);
        void RemoveEdge(NodeType fromNode, NodeType toNode, EdgeType label);
        void ClearEdges(EdgeType label);
    }

    /// <summary>
    /// An interface for attaching data to node handles.
    /// </summary>
    /// <typeparam name="NodeType">The type of a node handle.</typeparam>
    /// <remarks>
    /// This interface allows general graph algorithms to attach data to graph nodes.
    /// </remarks>
    internal interface CanCreateNodeData<NodeType>
    {
        /// <summary>
        /// Create a mapping from node handles to data.
        /// </summary>
        /// <typeparam name="T">The type of data to store.</typeparam>
        /// <returns>A mapping initialized to defaultValue.</returns>
        IndexedProperty<NodeType, T> CreateNodeData<T>(T defaultValue);
    }

    /// <summary>
    /// An interface for attaching data to edge handles.
    /// </summary>
    /// <typeparam name="EdgeType">The type of an edge handle.</typeparam>
    /// <remarks>
    /// This interface allows general graph algorithms to attach data to graph edges.
    /// </remarks>
    internal interface CanCreateEdgeData<EdgeType>
    {
        /// <summary>
        /// Create a mapping from edge handles to data.
        /// </summary>
        /// <typeparam name="T">The type of data to store.</typeparam>
        /// <returns>A mapping initialized to defaultValue.</returns>
        IndexedProperty<EdgeType, T> CreateEdgeData<T>(T defaultValue);
    }
}